package leetcode.tree;

import java.util.ArrayList;
import java.util.List;

public class Lc450 {

    List<Integer> list = new ArrayList<>();

    public TreeNode deleteNode(TreeNode root, int key) {
        getBSTList(root, key);
        if (list.size() == 0) return null;
        return buildBST(0, list.size() - 1);
    }
    private TreeNode buildBST(int l, int r) {
        if (l > r) return null;
        int mid = (l + r) / 2;
        TreeNode root = new TreeNode(list.get(mid));
        root.left = buildBST(l, mid - 1);
        root.right = buildBST(mid + 1, r);
        return root;
    }
    private void getBSTList(TreeNode node, int key) {
        if (node == null) return;
        getBSTList(node.left, key);
        if (key != node.val) {
            list.add(node.val);
        }
        getBSTList(node.right, key);
    }


}
